class Solution(object):
    def closestCost(self, baseCosts, toppingCosts, target):
        n = len(baseCosts)
        m = len(toppingCosts)
        min_diff = float('inf')
        min_val = float('inf')
        for i in range(n):
            if baseCosts[i] >= target:
                if baseCosts[i] - target < min_diff:
                    min_diff = baseCosts[i] - target
                    min_val = baseCosts[i]
            else:
                max_target = 2 * target - baseCosts[i]
                d = {baseCosts[i]}
                for j in range(m):
                    next_d = set()
                    for node in d:
                        next_d.add(node)
                        if node + toppingCosts[j] < max_target:
                            next_d.add(node + toppingCosts[j])
                        if node + 2 * toppingCosts[j] < max_target:
                            next_d.add(node + 2 * toppingCosts[j])
                    d = next_d
                for node in d:
                    diff = abs(target - node)
                    if diff < min_diff:
                        min_diff = diff
                        min_val = node
                    else:
                        if diff == min_diff:
                            min_val = min(min_val, node)
        return min_val
